Random data is useful in a variety of applications, some of which include weather forecasting, pricing of futures and chaos-theory based simulations in general, probability-based mathematics, access control, secure communications including cryptography and steganography, and cryptanalysis. Randomness is thus an important tool in science and technology.
In certain of the above applications, it is preferable for two separate parties to have simultaneous access to the same random data, and in many applications it is preferred to make such random data available in large quantities and/or in a consecutive manner. The two parties may be connected over an open network such as the PSTN (Public Switched Telephone Network) or the Internet or over a public radio network, and it may thus be further desirable that other users of the network do not have access to the same random data. An example of such an application is a secret key data encryption method, in which both parties need access to the same random secret keys. A further example is an access control system in which random data is used to provide a password to restrict access to a given facility. In all of these cases the security of the system relies upon the fact that only authorized parties, being at least two in number, have access to the random data.
Now, random data cannot be created simultaneously and separately at the two parties because if identical random data is generated simultaneously at two locations then it is by definition not random. If the random data is generated at one party and transmitted to the other party then it is vulnerable to interception by unauthorized parties.
Currently, two approaches are used. A first approach is to generate the random data at one of the parties and then either send it manually to the other party, for example by special courier, or by encrypting it and sending it electronically over the open lines.
A second approach is to have an identically set pseudo-random number generator (PRNG) at each party and one party sends a seed to the other party to start PRNG at the same ‘starting point’. A PRNG produces a stream of data which conforms to statistical measures of randomness, i.e. it may look like white noise, but if given an identical starting point will in fact produce an identical stream.
The current approaches are thus believed to lack efficiency (manual sending of the random data) or lack security (transmission of a seed or encryption of data using an encryption system, which by definition has to rely on a shorter key than the data itself) or lack randomness (reliance on PRNG).
Any improved approach to the problem would be required to supply identical random data to remote sites so that remote simultaneous use of the random data may be made. Furthermore, such supply must be confidential. Moreover, it is not sufficient that simultaneity and confidentiality are available. The two users must be convinced that they are synchronized, and that they are synchronized with each other and with no-one else. Furthermore, the parties must be able to regain synchronization in a secure fashion which they can trust and which does not permit admittance of eavesdroppers.
The above requirements are difficult to fulfill because of the so-called Byzantine agreement problem, which may be stated as follows:
Two remote armies, A and B, approach from different directions to besiege a powerful city. Neither army alone is powerful enough to overcome the city and should it appear on the battlefield alone it will be destroyed. Only if both armies appear simultaneously and from opposite directions is there any chance of success.
The overall commander, located with army A, has to co-ordinate an attack, but has at his disposal dispatch riders as his only means of communication.
The overall commander thus sends a message to the commander of Army B, by dispatch rider, which conveys time of and directions for the intended attack. However, having sent the message by a courier, the commander of army A cannot be certain that the message has reached its destination, (and if it has, that it has not been tampered with on the way). Thus, logic dictates that he will not attack, due to his instinct for self-preservation.
Having received the message, the commander of Army B is faced with the same problem, he cannot be certain that the content of the message is real and that it indeed comes from his ally. It could be a false message sent by the enemy and intended to lure him to his destruction. Furthermore, he knows that commander A has an instinct for self-preservation which is no less real than his own. Thus he must assume that A will not attack and hence he too, does not attack.
Furthermore, he knows that his ally, the commander of army A, will be faced with the same dilemma when receiving his acknowledgement and is unlikely to launch an attack on the basis of this information. Army B, in any case sends back to Army A an acknowledgment message, of the time of and directions for of the attack. Army A receives the acknowledgement but also cannot be sure that the acknowledgement is genuine and has not been sent by the enemy to lure them to their destruction. Furthermore, A knows of B's instinct for self-preservation. Bearing this in mind, army A must assume that army B will not attack. The situation is not improved however many further rounds of acknowledgement or confirmation are carried out. That is to say, having sent the acknowledgment message, both army A and army B keep facing the same dilemma of not being able to assume that the other will attack and, as a result, an attack will never be launched.
The “Byzantine Agreement Problem”, is a logical dilemma that is relevant when translated into modem communications, especially when considering for example, open communication modes such as the Internet, which are exposed to hackers, imposters etc. and to errors and breaks in communications.
The issues that this logical dilemma presents, and need to be solved are (i) synchronization; (ii) simultaneity; (iii) identification; and (iv) authentication.
At the basis of the problem lies the fact that at any given step, one party knows less than the other, and there is a lag between the knowledge of the parties (about the situation of one party in regard to the other party, and in their mutual understanding)
The Byzantine agreement problem thus raises the following issues, synchronization, simultaneity, identification and authentication. The root of the problem is that at any given leg of the communication procedure, one party leads and one party lags, even if by nanoseconds, thus leading to scope for dispute and for impersonation.
The depth of the problem may be demonstrated by illustrating two approaches that have been used in attempted solutions in the past. 1) Clock timing synchronization. Each party has an identically set clock. A parameter changes at predetermined clock settings. Unfortunately the two clocks cannot be set so accurately with respect to one another that no dispute occurs at any time. Even a difference of nanoseconds can lead to dispute over some of the data. 2) Synchronization by announcement. A parameter change is made upon receipt of a predetermined announcement. Unfortunately, this approach begs the very essence of the Byzantine agreement problem, since I do not know whether the other side has received the announcement, or whether it originates from a legitimate source at all.
There is thus a widely recognized need for, and it would be highly advantageous to have, a simple and practical way to produce identical ongoing randomness at seperate and remote locations, that is confidential by nature and which enables a mode of communication, synchronization or authentication between two parties that is not vulnerable to the logical dilemmas of the Byzantine agreement problem.
A limited solution, limited to encrypting messages between parties, is to be found in U.S. Pat. No. 5,703,948 which uses state machines to produce pseudo-random keys for the encryption of messages between parties.